//二分查找   力扣704
//二分查找用于：目标的值已知，需查找其位置的情况
//使用条件：已知位置与目标的对应关系或对应方法
//          查找的数据有序
//          查找对象的值已知
//（闭与开指的是：左指针和右指针当前所指向的位置是否包括在搜索范围内，因为左右指针是维护搜索边界的）
//left和right的初始化、while循环的条件、判断大小后的取值都要遵从一开始设定的“开闭”情况

//左闭右闭写法
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = 0;  //保证left在搜索范围内
		int right = nums.size() - 1;  //保证right在搜索范围内
		while(left <= right)  //根据左闭右闭，二者可以取等
		{
			int mid = (left+(right-left)/2); //防止溢出
			if(nums[mid] < target)  left = mid + 1; //保证left在搜索范围内
			else if(nums[mid] > target) right = mid - 1;//保证right在搜索范围内
			else return mid;  //找到了
		}
		return -1; //没找到
	}
};

//左闭右开写法
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = 0;  //保证left在搜索范围内
		int right = nums.size() ;  //保证right“不”在搜索范围内
		while(left < right)  //根据左闭右开，二者不能取等
		{
			int mid = (left+(right-left)/2); //防止溢出
			if(nums[mid] < target)  left = mid + 1; //保证left在搜索范围内
			else if(nums[mid] > target) right = mid;//保证right“不”在搜索范围内
			else return mid;  //找到了
		}
		return -1; //没找到
	}
};

//左开右开
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = -1;
		int right = nums.size();
		while(left + 1 != right)
		{
			int mid = left+(right-left)/2;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid;
			else return mid;
		}
		return -1;
	}
};

//左开右闭
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = -1;
		int right = nums.size() - 1;
		while(left < right)
		{
			int mid = left + (right - left)/2 + 1;
			if(nums[mid] < target) left = mid;
			else if(nums[mid] > target) right = mid - 1;
			else return mid;
		}
		return -1;
	}
};
